Esercitazione 4

Esercizio 4.1: esercizio d'esame 2023-01-10

Il testo con soluzione si trova qui.

Provare da sé

Provare a svolgere da sé l'esercizio, prima di guardare la soluzione o andare oltre per la discussione.

Per svolgere l'esercizio c'è bisogno di rammentare la teoria sulla moltiplicazione di numeri naturali, dal modulo di aritmetica. Lì si è visto che in una qualunque base $\beta$ mi basta saper fare la moltiplicazione tra numeri di una sola cifra, e saper scomporre le moltiplicazioni su più cifre in moltiplicazioni a una sola cifra con shift e somme.

Rinfreschiamo il concetto a partire da numeri in base 10, che è quella a cui siamo abituati. In questa base, saper fare le moltiplicazioni tra numeri di una sola cifra equivale a sapere le tabelline. Scomporre la moltiplicazione su più cifre altro non è che fare la moltiplicazione in colonna

  75 *
  23 =
----
  15 +
 21  +
 10  +
14   =
----
1725

Una parte importante della moltiplicazione in colonna è "spostare a sinistra" i prodotti tra cifre, che in forma più esplicita si fa mettendo degli zeri. Questo altro non è che moltiplicare il prodotto parziale per la giusta potenza di 10. Infine, partendo dal prodotto di numeri di 2 cifre ciascuno, si ha un risultato su 4 cifre. Questo procedimento è del tutto generalizzabile in qualunque base $\beta$.

Torniamo a noi: dobbiamo fare una moltiplicazione su 16 bit, usando solo istruzioni mul a 8 bit. Se consideriamo $\beta = 2^8$, questo è un prodotto tra numeri di due cifre e abbiamo tutti gli ingredienti necessari:

• il prodotto tra singole cifre lo sappiamo fare, perché è proprio la mul a 8 bit,
• sappiamo moltiplicare i prodotti parziali per potenze di $\beta$, ci basterà fare shl per 8 e 16 bit,
• sappiamo sommare i prodotti parziali, perché abbiamo la add a 32 bit che l'esercizio ci consente di usare.

Siano i due numeri x e y scritti come due cifre in base $2^8$, xh xl e yh yl. Allora si scompone la loro moltiplicazione come

            xh xl *
            yh yl =
-----------------
        (xl * yl) +
  (xh * yl) * 2^8 +
  (xl * yh) * 2^8 +
 (xh * yh) * 2^16 =
------------------
             x * y

Da qui, l'implementazione che ne segue è molto semplice.

Esercizio 4.2: esercizio d'esame 2023-09-12

Il testo con soluzione si trova qui.

Provare da sé

Provare a svolgere da sé l'esercizio, prima di guardare la soluzione o andare oltre per la discussione.

Trovare numeri primi è un problema molto studiato, soprattutto per le varie ottimizzazioni algoritmiche possibili e necessarie se si vuole affrontare la ricerca di primi molto grandi. Per questo esercizio non serve nulla di complicato.

Un numero non è primo se è divisible per almeno uno dei numeri primi precedenti, altrimenti è primo. Quindi se è nota la lista di numeri primi $p_1, ..., p_k$ minori del numero corrente $n$, ci basterà scorrere questa lista testando la divisione tra naturali $n / p_i$ e controllandone il resto. Se troviamo resto 0 per qualche $p_i$ (ne basta uno) il numero non è primo. Se arriviamo alla fine della lista senza mai trovare la condizione di sopra, il numero è primo. Lo aggiungiamo quindi alla lista e continuiamo oltre.

L'algoritmo di sopra è facilmente implementabile in assembler con l'aiuto di alcune ipotesi date dall'esercizio:

• Sappiamo il numero massimo di primi da considerare, cioè 50. La lista può quindi essere implementata con un vettore di 50 elementi e un contatore che indichi quante delle sue celle sono state riempite.
• Sappiamo che il massimo numero primo da considerare è $< 255$, ergo ci basteranno 8 bit.
• I primi due numeri primi, 2 e 3, sono da considerarsi già noti. Questo ci evita diverse complicazioni per i primi passaggi. Per esempio, sarà vero che nessun altro numero pari potrà essere primo e che si può incrementare di 2 alla volta per saltare da un numero dispari al successivo.

Da qui, l'implementazione dell'esercizio è solo questione di scorrimento del vettore e controllo di flusso. Nella soluzione proposta, vediamo che la ricerca del successivo numero primo è implementata con il sottoprogramma apposito find_next_prime, che si occupa della ricerca del numero e l'aggiunta in coda al vettore. La logica principale si limita a chiamare find_next_prime finché il contatore dei numeri primi non raggiunge quanto richiesto dall'utente, per poi stampare il vettore con la formattazione desiderata.